1. Field of the Invention
The present invention relates to an LDPC (Low Density Parity Check) decoder.
2. Discussion of the Related Art
LDPC decoding enables obtaining performance very close to the theoretical Shannon limit. LDPC decoders generally have better performance than turbo-code decoders and are currently used in broadcasting systems, for example, satellite digital television broadcasting systems.
The LDPC decoding consists, for a given word s containing k bits, of transmitting a word u containing n bits, among which n-k additional bits called parity bits which fulfill n-k parity equations. The matrix H having n-k lines and n columns verifying the following relation is called the code control matrix:H*tu=0  (1)
The size of the matrices H generally used is significant since they may comprise more than 60,000 columns and 50,000 lines. Further, such matrices are practically empty and may comprise one “1” for approximately 10,000 “0”s. This is why they are called low-density matrices.
The number of “1”s in the line is called the check node degree of a line and the number of “1”s in the column is called the bit node degree. There are two types of LDPC codes: regular codes and irregular codes. Matrix H of a regular code has a constant number of “1”s per line and per column. The check node and bit node degrees are then constant. An irregular code has no constant check node degrees and/or bit node degrees and has a more random character. However, the best performances are obtained for irregular codes. The problem of an irregular matrix is that it is random. The decoding can then be difficult. European digital satellite television standard DVB-S2 advocates for the use of a matrix H which has a constant check node degree, and a bit node degree that can take three values.
FIG. 1 shows a graph corresponding to an equivalent representation of a matrix H of an LDPC code. Each circle 10 represents a bit node. As an example, six bit nodes BNi, with i ranging from 0 to 5, are shown. Each square 12 represents a check node. As an example, four check nodes CNj, with j ranging from 0 to 3, are shown. Branches 14 connect given bit nodes BNi to given check nodes CNj. The presence of a branch 14 between a bit node of index i and a check node of index j means that the equivalent matrix H has a “1” at line j and at column i. Note Ne the total number of branches 14 in the graph. Number Ne thus corresponds to the number of “1”s of matrix H.
The matrix H equivalent to the graph shown in FIG. 1 is the following:
                    H        =                  (                                                    110010                                                                    101001                                                                    010110                                                                    001101                                              )                                    (        2        )            
Such a matrix H has a constant bit node degree equal to 2 and a constant check node degree equal to 3.
LDPC decoding uses log-likelihood ratios (LLR). For a transmitted information bit d to which corresponds a signal y received by the decoder after addition of the transmit channel noise, the LLR ratio of bit d with respect to signal y is defined as follows:
                              LLR          ⁡                      (            y            )                          =                              LLR            ⁡                          (                              d                ❘                y                            )                                =                      ln            ⁢                                          P                ⁡                                  (                                      ⅆ                                          =                                              0                        ❘                        y                                                                              )                                                            P                ⁡                                  (                                      ⅆ                                          =                                              1                        ❘                        y                                                                              )                                                                                        (        3        )            
where P(d=0|y) is the probability for transmitted bit d to be equal to 0 according to the received value y and P(d=1|y) is the probability for transmitted bit d to be equal to 1 according to the received value y. Such probabilities especially depend on the features of the transmit channel. The larger LLR(y), the greater the probability for transmitted bit d to be equal to “0”. As an example, it may be decided, for a received signal y, that if LLR(y) is negative, then transmitted bit d is a “1” and that, otherwise, transmitted bit d is a “0”.
LDPC decoding is based on a so-called message passing algorithm. Such an algorithm consists of associating with each bit node a received signal to which corresponds an initial LLR ratio, and of iteratively exchanging messages between bit nodes 10 and check nodes 12, along branches 14 of the graph corresponding to matrix H. The exchanged messages are log likelihood ratios and enable determining, after several iterations, for each received signal a corrected LLR ratio based on which the bit which has been transmitted is finally determined.
An iteration of such an algorithm mainly comprises two steps:
a “bit node determination” step which consists, for each bit node, of gathering the messages transmitted to the bit node by the check nodes to which the bit node is connected and of sending a new message to each check node to which the bit node is connected; and
a “check node determination” step which is the symmetrical operation and which consists, for each check node, of gathering the messages transmitted to the check node by the bit nodes to which the check node is connected and of sending a new message to each bit node to which the check node is connected.
It can actually be considered that each branch 14 corresponds to a memory element from which a message is read before each bit or check node determination step and into which a message is written after each bit or check node determination step.
LDPC decoding algorithm will now be more specifically described for a graph having dbn bit nodes BNi, i ranging from 0 to dbn-1, and dcn check nodes CNj, j ranging from 0 to dcn-1. For the first iteration, the bit node determination step is carried out by using, for each bit node BNi, value LLR(yi) where yi is the received signal associated with bit node BNi. Values LLR(yi) are obtained from the characteristics of the transmit channel. Message vi→j, called a bit node message, transmitted by bit node BNi to check node CNj, is initialized as follows:vi→j=LLR(yi)  (4)
The next check node determination step consists, for each check node CNj, of transmitting a message wj→i, called a check node message, to each bit node BNi connected to check node CNj. Each message wj→i is determined from the parity equation associated with check node CNj. For this purpose, the messages vk→j provided by the bit nodes BNk connected to check node CNj are simply used, except for bit node BNi to which message wj→i is transmitted, and message wj→i is obtained by verifying the parity equation. Let S1j be the subset of [0, dbn-1)] containing the indexes k such that bit nodes BNk are connected to check node CNj. The expression of wj→i is given by the following relation:
                              w                      j            ->            i                          =                  ln          (                                    1              +                                                ∏                                                            k                      ∈                      S1j                                        ,                                          k                      ≠                      i                                                                      ⁢                                                                  ⁢                                  tanh                  ⁡                                      (                                                                  v                                                  k                          ->                          j                                                                    /                      2                                        )                                                                                      1              -                                                ∏                                                            k                      ∈                      S1j                                        ,                                          k                      ≠                      i                                                                      ⁢                                                                  ⁢                                  tanh                  ⁡                                      (                                                                  v                                                  k                          ->                          j                                                                    /                      2                                        )                                                                                )                                    (        5        )            
For the next iterations, the bit node determination step is carried out, for each bit node BNi, based on messages wj→i provided by check nodes CNj connected to bit node BNi. For each check node CNj connected to bit node BNi, a message vi→j corresponding to the sum of initial value LLR(yi) and of all the messages received from the check nodes connected to bit node BNi, except for the message transmitted by node CNj, is provided. Let S2i be the subset of [0, dcn-1] containing indexes k such that check nodes CNk are connected to bit node BNi. The expression of vi→j thus is the following:vi→j=LLR(yi)+ΣkεS2i,k≠jwk→i  (6)
Once a determined number of iterations has been performed, a value Li corresponding to a corrected LLR ratio is determined for each bit node BNi. Li is determined by the following equation:
                              L          i                =                              LLR            ⁡                          (                              y                i                            )                                +                                    ∑                              k                ∈                S2i                                      ⁢                                                  ⁢                          w                              k                ->                i                                                                        (        7        )            
It is then decided, for each bit node BNi, based on value Li, which is the value of the bit associated with the received signal yi. For example, if Li is negative or zero, it may be decided that the bit is equal to 1 and if Li is strictly positive, it may be decided that the bit is equal to 0.
FIG. 2 schematically shows an example of the forming of an LDPC decoder 20 implementing the previously-described algorithm.
Decoder 20 comprises a processing unit 22 comprising NB separate elementary processing units 24 (Modj, j ranging from 1 to NB) capable of performing in parallel calculation operations to provide the bit and check node messages.
Decoder 20 comprises a RAM 26 in which are stored the bit node messages provided by units 24 after a bit node determination step and check node messages provided by units 24 after a check node determination step. Memory 26 comprises Ne/NB lines. At each line of memory 26 is stored a word containing a number of bits equal to the product of number NB of units 24 by the number of bits that can be processed by a unit 24. Each word corresponds to the juxtaposition of NB bit node messages or of NB check node messages.
Decoder 20 comprises an input memory 28 in which are stored initial values LLR(yi), i ranging from 0 to dbn-1. Decoder 20 also comprises an output memory 30 in which are stored values Li, i ranging from 0 to dbn-1.
Processing unit 22 is connected to a multiplexer 32, controlled by a control signal S1 which, according to the value of control signal S1, provides processing unit 22 with a word from input memory 28, a word directly read from memory 26, or a word provided by a rearrangement unit 34 and which corresponds to a word of memory 26 in which the order of the messages forming the word has been modified. More specifically, when a word is transmitted to processing unit 22, the message at the first position in the word is transmitted to the first elementary processing unit Mod1, etc., and the message at the NBth position in the word is transmitted to the NBth elementary processing unit ModNB.
Processing unit 22 is capable of successively providing words corresponding to the juxtaposition of NB bit node messages or of NB check node messages. More specifically, when a word is transmitted to processing unit 22, the message at the first position in the word is provided by first elementary processing unit Mod1, etc., and the message at the NBth position in the word is provided by the NBth elementary processing unit ModNB. The words provided by processing unit 22 may be transmitted to output memory 30 or to a rearrangement unit 38 capable of providing a new word from a received word and corresponding to the received word in which the order of the NB bit node messages or of the NB check node messages is modified.
Rearrangement unit 38 drives a first input of a multiplexer 40, controlled by a signal S3. Processing unit 22 drives a second input of multiplexer 40. According to the value of S3, multiplexer 40 provides memory 26 with the word provided by rearrangement unit 38 or by processing unit 22.
Decoder 20 comprises an address provision unit 42, for example, comprising a ROM, at each line of which are stored an address of memory 26 and rearrangement data. Rearrangement units 34 or 38 are capable of modifying the order of the messages in a word based on rearrangement data. The rearrangement data may correspond to a number of shift positions. By successively reading the lines of address provision unit 42, a series of addresses in memory 26 is obtained in an order different from the regular order of the reading from the lines of memory 26.
Upon operation of decoder 20, for a bit node determination step or for a check node determination step, an elementary unit 24 is brought to use bit or check node messages which are located at different locations in memory 26.
Generally, the messages are distributed in memory 26 so that, in a check node determination step, the words can be read successively according to the regular order of the reading from memory 26, the bit node message placed at the first position of each word of memory 26 being used by first elementary unit MOD1, etc., and the message placed at the NBth position being used by the NBth elementary unit MODNB. After a check node determination step, each check node message is stored at the same position as the bit node message previously associated with the same branch.
In the next bit node determination step, the rearrangement unit reads the words from memory 26 in the read order provided by address provision unit 42. For each read word, rearrangement unit 34 provides a new word corresponding to the read word in which the message order is modified based on the rearrangement datum of address provision unit 42. The messages are, for example, shifted to the left by a number of positions equal to the number of shift positions stored in address provision unit 42 for the read address. The message at the first position of the new word is then provided to first elementary unit Mod1, etc. and the message at the NBth position of the new word is provided to the NBth elementary processing unit ModNB.
From a word transmitted by processing unit 22, rearrangement unit 38 provides a new word that it stores in memory 26 according to an order provided by address provision unit 42 so that each bit node message is stored at the same location as the previous check node message associated with the same branch. For example, each new word corresponds to the received word in which the bit node messages are shifted to the right by a number of shift positions stored in address provision unit 42.
Memory 26 is generally of large size since Ne can be greater than 200,000. As an example, a processing unit 22 may contain several hundreds of elementary processing units 24 operating in parallel. If each message is coded over some ten bits, each word manipulated by rearrangement units 34, 38 comprises several thousands of bits. A rearrangement circuit capable of performing circular shift operations on such words can take up several square millimeters when it is formed on an integrated circuit according to a conventional semiconductor technology. This corresponds to a non-negligible portion of the total decoder surface area.